#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct stack{
    void * block[100];
    int p;
};

typedef struct node{
    char name;
    struct node * lchild;
    struct node * rchild;
}Node;

void push(struct stack * stk, void * item){
    stk->block[(stk->p)++] = item;
}

void * pop(struct stack * stk){
    return stk->block[--(stk->p)];
}

int is_empty(struct stack * stk){
    return (stk->p == 0);
}

void init(struct stack * stk){ stk->p = 0;
}

int is_op(char chr){
    return  chr == '+' ||
            chr == '-' ||
            chr == '*' ||
            chr == '/'
            ;
}
struct node *  postfix_to_tree(char * expr){
    int i;
    int len = strlen(expr);
    struct stack node_stk;
    init(&node_stk);
    struct node * cur_node;
    for (i=0; i<len; i++){
        cur_node = (struct node * ) malloc(sizeof(struct node));
        cur_node ->name = expr[i];
        cur_node ->lchild = NULL;
        cur_node ->rchild = NULL;
        if (is_op(expr[i])){
            cur_node->lchild = pop(&node_stk);
            cur_node->rchild = pop(&node_stk);
            push(&node_stk, cur_node);
        }else{
            push(&node_stk, cur_node);
        }
    }
    return cur_node;
}


int calc_depth(Node * root){
    if (root == NULL){
        return 0;
    }else {
        int l = calc_depth(root->lchild);
        int r = calc_depth(root->rchild);
        return l > r ? l+1 : r+1;
    }
}

/*把一个树映射到一个数组上
 */
void map_node(Node * root, Node ** node_array, int index){
    if(root != NULL){
        node_array[index] = root;
        map_node(root->lchild, node_array, index * 2);
        map_node(root->rchild, node_array, index * 2 + 1);
    }
}

void putchars(char chr, int cnt){
    while(cnt--)
        putchar(chr);
}

void print_tree(Node * root){
    int depth = calc_depth(root);
    int node_num =  (1 << depth) - 1;
    Node ** nodes = calloc(node_num + 1, sizeof(Node *));
    map_node(root,nodes,1);
    printf("Depth: %d\n", depth);
    int i, j,  space, element_num, cur_idx;
    cur_idx = 1;
    for (i=0; i< depth; i++){
        space =  1 << (depth - i + 1);
        element_num =  1 << i;
        //print elements
        for (j=0; j < element_num; j++){
            if (nodes[cur_idx+j] != NULL){
                printf("%*c%*c",space/2,nodes[cur_idx + j]->name,space/2,' ');
            } else {
                printf("%*c",space,' ');
            }
        }
        putchar('\n');
        if (i!=depth-1){ // print hands
            space = space/2;
            for (j=0; j < element_num; j++){
                printf("%*c",space/2,' ');
                if (nodes[(cur_idx+j)*2] != NULL){
                    putchars('_', space/2-2);
                    putchar('/');
                    putchar(' ');
                } else{
                    putchars(' ', space/2);
                }
                if (nodes[(cur_idx+j)*2+1] != NULL){
                    putchar('\\');
                    putchars('_', space/2-2);
                    putchar(' ');
                } else{
                    putchars(' ', space/2);
                }
                printf("%*c",space/2,' ');
            }
            putchar('\n');
        }
        cur_idx += j;
        //printf("index: %d, line: %d\n",cur_idx, i);
    }
}

int main(){
    char expr[] =  "abc*+de*f+g*+";
    printf("%s\n",expr);
    Node * result  =  postfix_to_tree(expr);
    print_tree(result);
    return 0;
}
